package org.example.myleet.p523;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    /**
     * 前缀和 + 同余原理 + 哈希表
     * 同余原理：
     * 当 prefixSums[q]−prefixSums[p] 为 k 的倍数时，prefixSums[p] 和 prefixSums[q] 除以 k 的余数相同
     * 利用这个原理可以再利用哈希快速找到上一个余数相同的坐标
     */
    public boolean checkSubarraySum(int[] nums, int k) {
        if (nums.length < 2) return false;
        long[] preSum = new long[nums.length];
        Map<Integer, Integer> remainderIndexMap = new HashMap<>();
        remainderIndexMap.put(0, -1);
        preSum[0] = nums[0];
        int remainder = (int) (preSum[0] % k);
        if (!remainderIndexMap.containsKey(remainder)) {
            //如果没有出现过才新增下标
            remainderIndexMap.put(remainder, 0);
        }
        for (int i = 1; i < nums.length; ++i) {
            preSum[i] = preSum[i - 1] + nums[i];
            remainder = (int) (preSum[i] % k);
            Integer index = remainderIndexMap.get(remainder);
            if (null != index) {
                if (Math.abs(i - index) >= 2) {
                    return true;
                }
            } else {
                //如果没有出现过才新增下标，可以保证下次找出来的下标都是最小的
                remainderIndexMap.put(remainder, i);
            }
        }
        return false;
    }

    /**
     * 前缀和再进行n^2遍历
     * 超时
     */
//    public boolean checkSubarraySum(int[] nums, int k) {
//        long[] preSum = new long[nums.length + 1];
//        preSum[0] = 0;
//        preSum[1] = nums[0];
//        for (int i = 1; i < nums.length; ++i) {
//            preSum[i + 1] = preSum[i] + nums[i];
//        }
//        for (int i = 1; i <= nums.length; ++i) {
//            int end = nums.length - i;
//            for (int j = 0; j <= end; ++j) {
//                long sum = preSum[j + i] - preSum[j];
//                if (sum % k == 0) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
}
